﻿//在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。
//请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
//
//输入：record = [9, 7, 5, 4, 6]
//输出：8
//解释：交易中的逆序对为(9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
//
//提示：
//	0 <= record.length <= 50000

class Solution {
    int tmp[50010];

public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return 0;
        int ret = 0;
        // 1.找中间点，将数组分成两部分

        int mid = (left + right) >> 1;
        // [left, mid][mid + 1, right]
        // 2.左边的个数+排序+右边的个数+排序

        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 3.⼀左⼀右的个数

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) // 升序的时候

        {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            }
            else {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        // 4.处理⼀下排序

        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= right)
            tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++)
            nums[j] = tmp[j - left];

        return ret;
    }
};